Tháng 10/1991 Tyahnybok gia nhập Đảng Quốc xã Ukraina (tiếng Ukraina: Соціал-національна партія України, SNPU) [7]. Ông được mô tả như là đại diện của cánh Ukraina cực hữu. Từ năm 1994 đến năm 1998, Tyahnybok là thành viên Hội đồng tỉnh Lviv [8]. Năm 1998, Tyahnybok lần đầu tiên được bầu vào Verkhovna Rada với tư cách thành viên Đảng Quốc xã Ukraina [7]. Trong quốc hội ông là thành viên của phái Phong trào nhân dân Ukraina (tiếng Ukraina: Народний Рух України, Narodnyi Rukh Ukrajiny) [7].

Năm 2002, Tyahnybok tái đắc cử Verkhovna Rada như một thành viên "khối Ukraina của chúng ta" của Victor Yushchenko. Ông đã trình 36 dự luật lên quốc hội cho tranh luận, nhưng chỉ thông qua bốn. Phần lớn dự luật này là vấn đề: phản đối sự duy trì tiếng Nga như là ngôn ngữ chính thức nhà nước thứ hai; đề nghị công nhận vai trò chiến đấu của Tổ chức Quốc dân Ukraina và Quân đội nổi dậy Ukraina trong Thế chiến thứ 2; kêu gọi cho lễ tẩy uế (quy định về sự tham gia chính trị) cho các quan chức trước đây là cộng sản và nhân viên an ninh mật vụ; và yêu cầu lệnh cấm của hệ tư tưởng cộng sản. Tuy nhiên chúng không được thông qua [9].

Ngày 20/07/2004 Tyahnybok bị trục xuất khỏi khối Ukraina của chúng ta [7][10], sau khi ông có bài phát biểu tại mộ của một chỉ huy Quân đội nổi dậy Ukraina ở dãy núi Karpat. Trong bài phát biểu, được phát sóng trên truyền hình vào mùa hè năm 2004, ông đã tuyên bố [11]:

"[Bạn là người] mà đám mafia Moskva-Do Thái đang cầm quyền ở Ukraina sợ nhất"[10]

và rằng:

"Họ đã không sợ và chúng ta không được sợ. Họ đã khoác khẩu súng tự động lên cổ và đi vào rừng, chiến đấu chống lại bọn Nga, Đức, Do Thái và đám cặn bã khác muốn lấy đi nhà nước Ukraina của chúng ta."[9]

Trong lời giải thích Tyahnybok cho biết ông không xúc phạm người Nga khi gọi họ một lực lượng chiếm đóng, mà sự thể được dựa trên sự kiện lịch sử. Ông cũng phủ nhận rằng ông bài Do Thái, mà chỉ là "pro-Ukraina" [12][13]. Văn phòng công tố ban đầu cáo buộc tội kích động hận thù dân tộc, nhưng sau đó đã rút vì thiếu chứng cứ. Tyahnybok đã thắng trong chín vụ việc liên quan đến tòa án về vấn đề đó. Các quyết định của tòa án đã được coi là bất hợp pháp, và hành động của kênh truyền hình "Inter" cho thấy các cảnh quay bài phát biểu Tyanybok, cũng như Derzhkomnatsmihratsia (công tố?) H. Moskal được coi là những người xúc phạm danh dự và nhân phẩm của Oleh Tyahnybok và gây ra thiệt hại cho đạo đức. Những hành động xung quanh vấn đề này dẫn đến việc tạo ra "Chương trình bảo vệ của Ukraina". Năm 2012 Tyahnybok tuyên bố rằng "bài phát biểu này là có liên quan đến ngày nay" và rằng "Tất cả tôi đã nói rồi, tôi cũng có thể lặp lại ngay bây giờ" [3].

Từ tháng 02/2004 Tyahnybok là lãnh đạo "Liên đoàn Tự do toàn Ukraina" tức Đảng Svoboda [8]. Tháng Tư năm 2005, Tyahnybok đã cùng ký một bức thư ngỏ đến Tổng thống Yushchenko kêu gọi một cuộc điều tra của quốc hội về "hoạt động tội phạm có tổ chức của người Do Thái ở Ukraina."[3][14]

Năm 2008 Tyahnybok ứng cử thị trưởng Kiev và được 1.37% phiếu. Năm 2010 ông ứng cử tổng thống với tư cách lãnh tụ Đảng Svoboda và được 1.43% tổng phiếu [15], phần lớn từ vùng Halychyna, Lviv, Ternopil và Ivano-Frankivsk.

Trong cuộc bầu cử địa phương năm 2010 đảng của Tyahnybok giành được giữa 20 và 30 % phiếu ở Đông Galicia, nơi nó đã trở thành một trong những lực lượng chính trong chính quyền địa phương [4][16].

Năm 2012 Tyahnybok tái đắc cử quốc hội, đảng của ông giành được 38 ghế [17][18][19], và ông trở thành lãnh đạo nhóm của đảng tại quốc hội [20].

Tháng 6/2013, Tyahnybok và một nhà lãnh đạo Đảng Svoboda đã bị cấm vào Mỹ do thái độ chống Do Thái công khai của họ, theo tờ báo Sevodnya (Ngày nay) ở Kiev [21].

Tháng 3/2014 nước Nga đã phát lệnh truy tố hình sự chống lại Tyahnybok và một số thành viên trong nhóm Tự vệ Nhân dân Ukraina của Quốc hội Ukraina, về việc "tổ chức nhóm vũ trang" đã bị cáo buộc chiến đấu chống lại Sư đoàn Phòng vệ đường không số 76 của Nga trong cuộc Chiến tranh Chechnya thứ nhất [22].

Năm 2014 trong cuộc bầu cử tổng thống Ukraina ông thu được 1,16% số phiếu bầu [23]. Trong cuộc bầu cử quốc hội tháng 10/2014 Tyahnybok một lần nữa đã đầu trong danh sách bầu cử của đảng ông. Song đảng này không vượt qua được ngưỡng 5% số phiếu bầu để có ghế trong quốc hội, tức là ông đã không được tái cử [24][25].